It is often desirable to analyze various aspects of the waveform of a signal. For example, a waveform is often characterized or described by determining and displaying its amplitude as a function of time using an oscilloscope or other data acquisition device. A waveform may also characterized in the frequency domain, i.e. a characteristic (magnitude, phase, etc.) of one or more of its frequency components.
One way of determining the magnitudes of the frequency components of an input time domain signal is using a fast Fourier transform (FFT). The theory of the FFT, as well as algorithms with which one may perform an FFT, also called a discrete Fourier Transform (DFT), are well known. A description of the FFT is given in Cooley, et al., "The Finite Fourier Transform", IEEE Trans. On Audio Elec., June 1969. Another type of transform is the DHT (discrete Hartley transform), and is described in, for example, O'Neill, "Faster Than Fast Fourier", Byte, April 1988, pp 293-300.
For both time domain and frequency domain analysis, a data acquisition system may be used to collect data regarding the waveform, and either analyze or display the waveform. A digital data acquisition system such as a digital oscilloscope receives and digitizes a continuous analog input. The digitized data, in the form of magnitude data as a function of time, is stored in a memory. The memory commonly is circular; that is, the memory is continuously re-written with the newest sample datum replacing the oldest sample datum until a trigger event occurs, at which point rewriting of the memory is stopped such that the data either before or after the trigger event (or some of both) is saved in the memory for analysis.
Trigger events have typically been based on the time domain input signal. For example, a trigger event may be the time domain input signal rising above a given magnitude. Another trigger event could be the slope of the time domain exceeding a given level. There have been numerous types of trigger events used, but they generally are responsive to a time domain characteristic of the signal.
Frequency domain triggering has not been generally used because it requires that a DFT, which is computationally difficult, be performed on the incoming data before the relevant signal data in the memory is written over. According to known methods of determining a DFT the digitizing rate must be limited to a few tens of kilohertz (kHz) to allow sufficient time to calculate a DFT before new data is written into the memory to replace the data on which the DFT calculation was based. This limitation, of course, limits the allowable frequency content of the signal being analyzed. The known methods of determining a DFT in a useful time frame also require that the number of points be limited, thereby limiting the spacing of the frequency bins of interest. In addition, while often only a few frequency bins are of interest, computing a DFT according to the prior art generally results in data for all frequency bins, requiring the time consuming performance of needless calculations.
One prior method of calculating a DFT, known as the Sliding DFT (SDFT), is described in Springer, "Sliding FFT Computes Frequency Spectra In Real Time", EDN, Sep. 29, 1988. Equation 1 below shows the SDFT formula from the article by Springer, using somewhat different nomenclature: ##EQU1## where k is the frequency bin index, N is the number of points in the DFT, x(n) is the magnitude of the time domain datum at the sample "n" where n is the time domain index, and X(k,l) is the complex amplitude in frequency bin k (the DFT for frequency k at time index l). The SDFT calculates a DFT for N points, from l to l+N-1, by updating the previous DFT (for the N points from l-1 to l+N-2). The updating is accomplished by subtracting the time domain magnitude of the first point in the previous DFT, x(l-1), and adding the amplitude of the latest time domain point, x(l+N-1). The sum is then multiplied by a phase shifting factor, e.sup.j2.pi.k/N. For the purposes of calculating the SDFT, the time reference point (t=0) is the first point in each DFT update. In other words, the zero time point is changed with each SDFT update. The calculations needed to obtain the updated DFT for each frequency bin k are two real adds and a complex multiply, or four real multiplies and four real adds, because the exponent and X(k,l-1) are complex and x(l+N-1) and x(l-1) are real. While this operation is much faster than calculating the DFT from scratch, it is still not fast enough for most frequency triggering operations.